package AlgorithmStudy.study.study01;

import java.util.Arrays;

/**
 * 快排
 * 两个数字指针
 * 一定先减后加
 * 先 r--
 * 后 l++
 */
public class QuickSort {

    public static void mai1n(String[] args) {
//        findKthLargest(new int[]{2,1}, 1);
//        findKthLargest(new int[]{3,2,1,5,6,4}, 2);
        findKthLargest(new int[]{3,1,2,4}, 2);
    }
    public static int findKthLargest(int[] nums, int k) {
        // 快排
        quickSort(nums, 0, nums.length-1);

        System.out.println(Arrays.toString(nums));
        System.out.println(nums[k-1]);
        return nums[k-1];

    }

    public static void quickSort(int[] arr, int l, int r){
        if(l>=r){
            return;
        }
        int i = l, j=r;
        // 基准值
        int temp = arr[l];
        while(i<j){
            // 左侧都是 大于等于基准值的
            if(arr[i] >= temp ){
                i++;
            }
            // 右侧都是小于基准值的
            if(arr[j] <= temp ){
                j--;
            }

            // 交换
            if(i<j){
                swap(arr, i, j);
            }

        }

        // 遍历完后 交换 基准值和大于值得边界
        swap(arr, l, i);

        quickSort(arr, l, i-1);
        quickSort(arr, i+1, r);


    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
//        int[] arr = new int[]{3,1,2,4};
        int[] arr = new int[]{3,2,1,5,6,4};
        quickSort1(arr,0, 5);
//        quickSortDescending(arr,0, 5);
//        quickSort2(arr,0, 5);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 从小往大 排序
     * 一定 左下标递增 先找到大于基准值的
     * 然后再右下标递减 找到小于基准值的
     * @param nums
     * @param l
     * @param r
     */
    private static void quickSort1(int[] nums, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) {
            return;
        }
        // 哨兵划分操作（以 nums[l] 作为基准数）
        int i = l, j = r;
        while (i < j) {
            // 必须先判断j 后判断i
            while (i < j && nums[j] >= nums[l]) {
                j--;
            }
            while (i < j && nums[i] <= nums[l]) {
                i++;
            }
            swap(nums, i, j);
        }
        swap(nums, i, l);

        quickSort1(nums, l, i - 1);
        quickSort1(nums, i + 1, r);
    }


    /**
     * 从大往小排列
     * 一定 右下标递减 先找到小于基准值的
     * 然后再左下标递增 找到大于基准值的
     * @param arr
     * @param l
     * @param r
     */
    public static void quickSort2(int[] arr, int l, int r){
        if(l>=r){
            return;
        }
        int i = l, j=r;
        while(i<j){
            // 右侧都是小于基准值的
            while(i<j && arr[j] <= arr[l]){
                j--;
            }
            // 左侧都是 大于等于基准值的
            while( i<j && arr[i] >= arr[l]){
                i++;
            }

            // 交换
            swap(arr,i,j);
        }

        // 遍历完后 交换 基准值和大于值得边界
        swap(arr, i, l);

        quickSort2(arr, l, i-1);
        quickSort2(arr, i+1, r);


    }

    /**
     * GPT 答案
     * @param nums
     * @param l
     * @param r
     */
    private static void quickSortDescending(int[] nums, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分操作（以 nums[l] 作为基准数）
        int i = l, j = r;
        while (i < j) {
            while (i < j && nums[j] <= nums[l]) {
                j--; // 逆向判断
            }
            while (i < j && nums[i] >= nums[l]){
                i++; // 逆向判断
            }
            swap(nums, i, j);
        }
        swap(nums, i, l);
        // 递归处理左（右）子数组，执行逆向划分
        quickSortDescending(nums, l, i - 1);
        quickSortDescending(nums, i + 1, r);
    }





}
